package 数据结构专栏.A_二叉树专栏.A_遍历问题;

import 数据结构专栏.A_二叉树专栏.TreeNode;

import java.util.*;

/**
 * @Title
 * @Author zhengqiang.tan
 * @Date 2021/4/17 3:02 PM
 */
public class 前中后序遍历 {


    /**
     * 1. 前序遍历 根 左 右
     * 时间复杂度：O(n)O(n)，其中 nn 是二叉树的节点数。每一个节点恰好被遍历一次。
     * 空间复杂度：O(n)O(n)，为递归过程中栈的开销，平均情况下为 O(\log n)O(logn)，最坏情况下树呈现链状，为 O(n)O(n)。
     **/
    public void preorderTraversal(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " "); // 当前节点
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
    }

    /**
     * 中序：左 根 右
     *
     * @param root
     * @return
     */
    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.val + " ");// 访问完左节点访问当前节点
            inorderTraversal(root.right);
        }
    }


    /**
     * 后序：左 右 根
     *
     * @param root
     * @return
     */
    public void postorderTraversal(TreeNode root) {
        if (root != null) {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.val + " ");
        }
    }


    /**
     * 迭代实现（栈）
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }


    public List<Integer> preorderTraversal_2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !s.isEmpty()) {
            if (cur != null) {
                res.add(cur.val); // root
                s.push(cur);
                cur = cur.left; // left
            } else {
                cur = s.pop();
                cur = cur.right; // right
            }
        }
        return res;
    }

    public List<Integer> inorderTraversal_2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left; // left
            } else {
                cur = stack.pop();
                res.add(cur.val); // root
                cur = cur.right; // right
            }
        }
        return res;
    }


    // 前序遍历顺序为：根 -> 左 -> 右
    // 后序遍历顺序为：左 -> 右 -> 根
    // 所以, 我们可以把前序遍历的稍作修改: 根 -> 右 -> 左,
    // 然后结果存放到栈里进行倒序, 之后再遍历结果栈就可以输出后序遍历了
    public List<Integer> postorderTraversal_2(TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        Stack<TreeNode> resStack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !s.isEmpty()) {
            if (cur != null) {
                resStack.push(cur); // root
                s.push(cur);
                cur = cur.right; // right
            } else {
                cur = s.pop();
                cur = cur.left; // left
            }
        }

        List<Integer> res = new ArrayList<>();
        while (!resStack.isEmpty()) {
            res.add(resStack.pop().val);
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildDemoTreeNode();
//        ------------------------------------------------------------
        new 前中后序遍历().preorderTraversal(root);//前序
        System.out.println();
        new 前中后序遍历().inorderTraversal(root);
        System.out.println();
        new 前中后序遍历().postorderTraversal(root);

        System.out.println();
        System.out.println("------------------------------");
        System.out.println(new 前中后序遍历().preorderTraversal2(root));
        System.out.println(new 前中后序遍历().inorderTraversal_2(root));
        System.out.println(new 前中后序遍历().postorderTraversal_2(root));

    }

}
